package com.liunian.algorithmstudy.monotonicstack;

import java.util.Stack;

public class Trap42 {

	/**
	 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

	 示例 1：
	 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
	 输出：6
	 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

	 示例 2：
	 输入：height = [4,2,0,3,2,5]
	 输出：9
	 */
	public int trap(int[] height) {
		Stack<Integer> stack = new Stack<>();
		stack.push(0);
		int sum = 0;
		for (int i = 1; i < height.length; i++) {
			if (height[stack.peek()] > height[i]) {
				stack.push(i);
			} else {
				while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
					Integer pop = stack.pop();
					if (!stack.isEmpty()) {
						sum += (Math.min(height[stack.peek()], height[i]) - height[pop]) * (i - stack.peek() - 1);
					}
				}
				stack.push(i);
			}
		}
		return sum;
	}

	public static void main(String[] args) {
		Trap42 trap = new Trap42();
		System.out.println(trap.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
	}

}
